from __future__ import annotations

import numpy as np

A = np.array(
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])

dle_A = []
tmp = None
cnt = 0
for i in A:
    if tmp is not None:
        if tmp == i:
            cnt += 1
        else:
            dle_A.append((cnt, tmp))
            tmp = i
            cnt = 1
    else:
        tmp = i
        cnt = 1
dle_A.append((cnt, tmp))
els = sorted(list(set(dle_A)), key=dle_A.index)
freq_table = list(map(lambda x: (x, dle_A.count(x)), els))
print("dle:", dle_A)
print("freq table:", freq_table)

# freq_table = [
#     ((1, 80), 1),
#     ((1, -1), 2),
#     ((1, 3), 2),
#     ((1, 0), 1),
#     ((1, 2), 1),
#     ((3, 0), 1),
#     ((1, 1), 2),
#     ((54, 0), 1),
#     ((63, 0), 2)
# ]


class Node:

    def __init__(self):
        self.left: Node | None = None
        self.right: Node | None = None
        self.sign: (int, int) = None
        self.freq: int = 0


tree_holder = list()

for i in freq_table:
    node = Node()
    node.sign = i[0]
    node.freq = i[1]
    tree_holder.append(node)
print("tree holder:", tree_holder)

if len(tree_holder) == 1:
    node = Node()
    node.left = tree_holder[0]
    tree_holder[0] = node

while len(tree_holder) != 1:
    leastNode1: Node = Node()
    leastNode2: Node = Node()
    leastNode1.freq = (-1 >> 1) & 0x7FFFFFFF
    leastNode2.freq = leastNode1.freq
    for i in tree_holder:
        if i.freq < leastNode1.freq:
            leastNode1 = i
    tree_holder.remove(leastNode1)
    for i in tree_holder:
        if i.freq < leastNode2.freq:
            leastNode2 = i
    tree_holder.remove(leastNode2)
    node = Node()
    node.left = leastNode1
    node.right = leastNode2
    node.freq = leastNode1.freq + leastNode2.freq
    tree_holder.insert(0, node)

print(tree_holder)


def dfs(root: Node | None, table: dict, current_code: str):
    if root is None:
        return
    if root.sign is not None:
        table[root.sign] = current_code
    dfs(root.left, table, current_code + '0')
    dfs(root.right, table, current_code + '1')


d = dict()
dfs(tree_holder[0], d, '')
print("huffman table:", d)
s = ''
for i in dle_A:
    s += d[i]
print("huffman code:", s)

decode_dle = list()
tmp = tree_holder[0]
for i in s:
    if i == '0':
        tmp = tmp.left
    elif i == '1':
        tmp = tmp.right
    if tmp.sign is not None:
        decode_dle.append(tmp.sign)
        tmp = tree_holder[0]
print("decode_dle:", decode_dle)


size = 0
for i in decode_dle:
    size += i[0]
zzag = np.ones(size, dtype=np.int32)
cnt = 0
for i in decode_dle:
    for j in range(i[0]):
        zzag[cnt] = i[1]
        cnt += 1
print("zzag:", zzag)